#leetcode题目31：下一个排列
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：双指针,数组
#注意事项：需要原地修改数组


#第二个视频合集

from typing import List
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i=len(nums)-2
        while i>=0 and nums[i]>=nums[i+1]:
            i-=1
        if i>=0:
            j=len(nums)-1
            while j>=0 and nums[j]<=nums[i]:
                j-=1
            nums[i],nums[j]=nums[j],nums[i]
        left,right=i+1,len(nums)-1
        while left<right:
            nums[left],nums[right]=nums[right],nums[left]
            left+=1
            right-=1
    #此处无需return，因为nums是原地修改的

        


#测试数据
nums=[1,2,3]
#预期输出：[1,3,2]
solution=Solution()
solution.nextPermutation(nums)
print(nums)

nums=[3,2,1]
#预期输出：[1,2,3]
solution=Solution()
solution.nextPermutation(nums)
print(nums)         

nums=[1,1,5]
#预期输出：[1,5,1]
solution=Solution()
solution.nextPermutation(nums)
print(nums)

#以上为示例，增加一个额外测试，视频中举例的
nums=[4,5,2,6,3,1]
#预期输出：[4,5,3,1,2,6]
solution=Solution()
solution.nextPermutation(nums)
print(nums)


